1. Field of the Invention
This invention relates to an optimization apparatus used to solve optimization problems such as a traveling-salesman problem and an n-queen problem.
2. Description of the Related Art
Optimization problems include the problem of optimizing the module arrangement in an LSI in terms of combination, taking into account an overall wiring length and other factors, and the problem of allocating intercommunicative processes to processors. They also include restoration, edge extraction, binary representation in the field of image processing as well as various problems related to graph theory.
An apparatus suitable for solving such optimization problems is disclosed in U.S. Pat. No. 4,660,166 (Hopfield). This apparatus solves an optimization problem by assigning the minimum point of the energy function as the optimum solution on the basis of the nature that an energy function for an interconnection type neural network with feedback but no layer structure decreases with state transition. However, such an energy function has many local minimums, so that it is difficult to approach the true optimum solution. To overcome this drawback, another model has been proposed which allows probabilistic state transition, thereby enabling simulated annealing techniques to improve convergence at the optimum solution.
Even with such techniques, however, it takes an emormously long time to obtain the optimum solutions.
A data processing apparatus to obtain the combination optimum solution, an improved version of the above U.S. patent, is disclosed in Published Unexamined Japanese Patent Application No. 2-210574 (Hitachi). In addition, a task allocation apparatus, an optimization apparatus similar to the foregoing U.S. patent, is disclosed in Published Unexamined Japanese Patent Application No. 2-81257 (Toshiba). These prior art apparatuses both use an interconnection type neural network as in the above U.S. patent. Therefore, with conventional optimization apparatus, it is very difficult to obtain the optimum solution to an optimization problem at a high speed with a high accuracy.